//最⻓回⽂⼦序列（medium）:https://leetcode.cn/problems/longest-palindromic-subsequence/
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n)); // 搞⼀个 dp 表
        for (int i = n - 1; i >= 0; i--)           // 枚举左端点 i
        {
            dp[i][i] = 1;                   // 填表的时候初始化
            for (int j = i + 1; j < n; j++) // 然后从 i + 1 的位置枚举右端点
            {
                // 分两种情况填写 dp 表
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        // 返回结果
        return dp[0][n - 1];
    }
};

//让字符串成为回⽂串的最⼩插⼊次数（hard）: https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n)); // 创建 dp 表
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
                else
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
        return dp[0][n - 1];
    }
};